//https://leetcode.cn/problems/binary-tree-level-order-traversal/
//二叉树层序遍历

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q1, q2;
        q1.push(root);
        vector<vector<int>> ret;
        vector<int> tmp;
        while(!q1.empty() || !q2.empty())
        {
            TreeNode* cur = nullptr;
            if(!q1.empty())
            {
                while(!q1.empty())
                {
                    if((cur = q1.front()) != nullptr)
                    {
                        tmp.push_back(cur->val);
                        q2.push(cur->left);
                        q2.push(cur->right);
                    }
                    q1.pop();
                }
            }
            else
            {
                while(!q2.empty())
                {
                    if((cur = q2.front()) != nullptr)
                    {
                        tmp.push_back(cur->val);
                        q1.push(cur->left);
                        q1.push(cur->right);
                    }
                    q2.pop();
                }
            }
            if(!tmp.empty())
                ret.push_back(tmp);
            tmp.clear();
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ret;
        
        int levelCount = 0;
        if(root != nullptr)
            q.push(root);

        while(!q.empty())
        {
            levelCount = q.size();
            vector<int> tmp;
            while(levelCount--)
            {
                TreeNode* cur = q.front();
                q.pop();
                tmp.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};